package problem140_Word_Break_II;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class MySolution {
	public List<String> wordBreak(String s, Set<String> wordDict) {
		Map<Integer,List<Integer>> dp=new HashMap<>();
		dp.put(0, new ArrayList<>());
		for(int i=1;i<=s.length();i++){
			for(int j=i-1;j>=0;j--){
				if(dp.get(j)!=null&&wordDict.contains(s.substring(j,i))){
					if(dp.get(i)==null)
						dp.put(i, new LinkedList<>());
					dp.get(i).add(j);
				}
			}
		}
		if(dp.get(s.length())==null)
			return new LinkedList<>();
		List<String> result=new LinkedList<>();
		dfs(result,new LinkedList<>(),dp,s,s.length());
		return result;
	}
	
	private void dfs(List<String> result,List<String> tmp,Map<Integer,List<Integer>> dp,String s,int end){
		if(end==0){
			StringBuilder sb=new StringBuilder();
			for(String t :tmp){
				sb.append(t);
			}
			String res=sb.toString();
			res=res.substring(0, res.length()-1);
			result.add(res);
			return;
		}
		List<Integer> next=dp.get(end);
		for(int n:next){
			tmp.add(0,s.substring(n,end)+" ");
			dfs(result,tmp,dp,s,n);
			tmp.remove(0);
		}
	}
	
	public static void main(String[] args){
		System.out.println(new MySolution().wordBreak("catsanddog", new HashSet<>(Arrays.asList(new String[]{"cat", "cats", "and", "sand", "dog"}))));
	}
}
